import java.util.HashMap;
import java.util.Map;

/**
 * 和为 K 的子数组
 * 给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的子数组的个数 。
 * 子数组是数组中元素的连续非空序列。
 * 示例 1：
 * 输入：nums = [1,1,1], k = 2
 * 输出：2
 * 示例 2：
 * 输入：nums = [1,2,3], k = 3
 * 输出：2
 */
public class demo11 {
    public int subarraySum(int[] nums, int k) {
        Map<Integer,Integer> hash = new HashMap<>();
        hash.put(0,1);
        int sum = 0, ret = 0;
        for (int x : nums){
            sum += x;
            ret += hash.getOrDefault(sum - k,0);
            hash.put(sum,hash.getOrDefault(sum,0)+1);
        }
        return  ret;
    }

    /**
     * 和可被 K 整除的子数组
     给定一个整数数组 nums 和一个整数 k ，返回其中元素之和可被 k 整除的（连续、非空） 子数组 的数目。
     子数组 是数组的 连续 部分。
     示例 1：
     输入：nums = [4,5,0,-2,-3,1], k = 5
     输出：7
     解释：
     有 7 个子数组满足其元素之和可被 k = 5 整除：
     [4, 5, 0, -2, -3, 1], [5], [5, 0], [5, 0, -2, -3], [0], [0, -2, -3], [-2, -3]
     示例 2:
     输入: nums = [5], k = 9
     输出: 0
     */
    public int subarraysDivByK(int[] nums, int k) {
        Map<Integer,Integer> hash = new HashMap<>();
        hash.put(0 % k,1);
        int sum = 0, ret = 0;
        for (int x : nums){
            sum += x;
            int r = (sum % k + k) % k;
            ret += hash.getOrDefault(r,0);
            hash.put(r,hash.getOrDefault(r,0)+1);
        }
        return ret;
    }
}
